package leetcode.每日一题;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author :songyaozhang
 * @date :Created 2021/8/11 10:41
 * @description :https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/
 */
public class 最长递增子序列的个数 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.findNumberOfLIS(new int[]{1,3,5,4,7}));
    }

    // 动态规划
    class Solution {
        public int findNumberOfLIS(int[] nums) {
            int n = nums.length;
            if (n == 0) return 0;
            int[] dp = new int[n];
            dp[0] = 1;
            int max = 1;
            for (int i = 1; i < n; i++) {
                dp[i] = 1;
                for (int j = 0; j < i; j++) {
                    if (nums[i] > nums[j]) {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
                max = Math.max(max, dp[i]);
            }
            int count = 0;
            for (int d : dp) {
                if (d == max) count++;
            }
            System.out.println(Arrays.toString(dp));
            return count;
        }
    }
}
